{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Task Scheduler II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: taskSchedulerII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #任务调度器 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的正整数数组&nbsp;<code>tasks</code>&nbsp;，表示需要 <strong>按顺序</strong>&nbsp;完成的任务，其中&nbsp;<code>tasks[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;件任务的 <strong>类型</strong>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个正整数&nbsp;<code>space</code>&nbsp;，表示一个任务完成&nbsp;<strong>后</strong>&nbsp;，另一个&nbsp;<strong>相同</strong>&nbsp;类型任务完成前需要间隔的&nbsp;<strong>最少</strong>&nbsp;天数。</p>\n",
    "\n",
    "<p>在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>完成&nbsp;<code>tasks</code>&nbsp;中的下一个任务</li>\n",
    "\t<li>休息一天</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回完成所有任务所需的 <strong>最少</strong>&nbsp;天数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [1,2,1,2,3,1], space = 3\n",
    "<b>输出：</b>9\n",
    "<strong>解释：</strong>\n",
    "9 天完成所有任务的一种方法是：\n",
    "第 1 天：完成任务 0 。\n",
    "第 2 天：完成任务 1 。\n",
    "第 3 天：休息。\n",
    "第 4 天：休息。\n",
    "第 5 天：完成任务 2 。\n",
    "第 6 天：完成任务 3 。\n",
    "第 7 天：休息。\n",
    "第 8 天：完成任务 4 。\n",
    "第 9 天：完成任务 5 。\n",
    "可以证明无法少于 9 天完成所有任务。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [5,8,8,5], space = 2\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>\n",
    "6 天完成所有任务的一种方法是：\n",
    "第 1 天：完成任务 0 。\n",
    "第 2 天：完成任务 1 。\n",
    "第 3 天：休息。\n",
    "第 4 天：休息。\n",
    "第 5 天：完成任务 2 。\n",
    "第 6 天：完成任务 3 。\n",
    "可以证明无法少于 6 天完成所有任务。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tasks.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= tasks[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= space &lt;= tasks.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [task-scheduler-ii](https://leetcode.cn/problems/task-scheduler-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [task-scheduler-ii](https://leetcode.cn/problems/task-scheduler-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,2,3,1]\\n3', '[5,8,8,5]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = dict()    # 储存这一任务上一次完成的时间\n",
    "        time = 0\n",
    "        for t in tasks:\n",
    "            if t in d and time < space + d[t] + 1:\n",
    "                time = space + d[t]\n",
    "            d[t] = time = time + 1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: list[int], space: int) -> int:\n",
    "        t = 0\n",
    "        map = {}\n",
    "        for i in range(0, len(tasks)):\n",
    "            v = tasks[i]\n",
    "            if (memory:=map.get(v, None)) != None:\n",
    "                if t - memory <= space:\n",
    "                    t = t + space-t+memory+1\n",
    "            map[v] = t\n",
    "            t = t+1\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans, last = 0, {}\n",
    "        for t in tasks:\n",
    "            ans +=1\n",
    "            if t in last:\n",
    "                ans = max(ans, last[t] + space +1)\n",
    "            last[t] = ans\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], k: int) -> int:\n",
    "        n, min_next, result = len(tasks), {}, 0\n",
    "        if n == 0: return 0\n",
    "        for task in tasks:\n",
    "            if task not in min_next or result >= min_next[task]:\n",
    "                result += 1\n",
    "            else:\n",
    "                result = min_next[task] + 1\n",
    "            min_next[task] = result + k\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        day = 1\n",
    "        hash = {}\n",
    "        for x in tasks:\n",
    "            if x in hash and day - hash[x] <= space:\n",
    "                day = hash[x] + space + 1\n",
    "            hash[x] = day\n",
    "            day += 1\n",
    "        return day - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        last_idx = {}\n",
    "        rest = 0\n",
    "        for i, task in enumerate(tasks):\n",
    "            if task not in last_idx:\n",
    "                last_idx[task] = i + rest\n",
    "            else:\n",
    "                j = last_idx[task]\n",
    "                rest += max(0, space-i-rest+j+1)\n",
    "                last_idx[task] = i + rest\n",
    "        return rest + len(tasks)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for task in tasks:\n",
    "            ans += 1\n",
    "            if task in dic.keys():\n",
    "                ans = max(ans,dic[task]+space+1)\n",
    "            dic[task] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = {}\n",
    "        cur = 0\n",
    "        for i, x in enumerate(tasks):\n",
    "            if x in d:\n",
    "                cur = max(d[x] + space, cur)\n",
    "            d[x] = cur + 1\n",
    "            cur += 1\n",
    "        return cur\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = dict()    # 储存这一任务上一次完成的时间\n",
    "        time = 0\n",
    "        for t in tasks:\n",
    "            if t in d and time < space + d[t] + 1:\n",
    "                time = space + d[t]\n",
    "            d[t] = time = time + 1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans, last = 0, {}\n",
    "        for t in tasks:\n",
    "            ans += 1  # 完成该任务，天数+1\n",
    "            if t in last:\n",
    "                ans = max(ans, last[t] + space + 1)  # 看看是否要间隔 space 天\n",
    "            last[t] = ans  # 记录上一次完成时间\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        sum = 0\n",
    "        record = dict()\n",
    "        last = []\n",
    "        for i in tasks:\n",
    "            if i not in record:\n",
    "                sum += 1\n",
    "                record[i] = sum\n",
    "            else:\n",
    "                if sum - record[i] < space:\n",
    "                    sum = space + record[i]\n",
    "                sum += 1\n",
    "                record[i] = sum\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        sum = 0\n",
    "        record = dict()\n",
    "        last = []\n",
    "        for i in tasks:\n",
    "            if i not in record:\n",
    "                sum += 1\n",
    "                record[i] = sum\n",
    "            else:\n",
    "                if sum - record[i] < space:\n",
    "                    sum = space + record[i]\n",
    "                sum += 1\n",
    "            record[i] = sum\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans,last=0,{}\n",
    "        for t in tasks:\n",
    "            ans+=1\n",
    "            if t in last:\n",
    "                ans=max(ans,last[t]+space+1)\n",
    "            last[t]=ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        lastMap = {}\n",
    "        day = 1\n",
    "        space += 1\n",
    "        for n in tasks:\n",
    "            last = lastMap.get(n, -space)\n",
    "            if day - last < space:\n",
    "                day = last + space\n",
    "            lastMap[n] = day\n",
    "            day +=1\n",
    "        return day - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i,t in enumerate(tasks):\n",
    "            if cnt[t] != 0 and ans-cnt[t]<space:\n",
    "                ans += space-ans+cnt[t]\n",
    "            ans += 1\n",
    "            cnt[t] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = {}\n",
    "        cur = 0\n",
    "        for x in tasks:\n",
    "            cur += 1\n",
    "            if x in d:\n",
    "                cur = max(d[x] + space + 1, cur)\n",
    "            d[x] = cur\n",
    "            \n",
    "        return cur\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "\n",
    "        ans = 1\n",
    "        mp = {}\n",
    "        for i, t in enumerate(tasks, 1):\n",
    "            if t not in mp:\n",
    "                mp[t] = ans\n",
    "                ans += 1\n",
    "            else:\n",
    "                if ans - mp[t] > space:\n",
    "                    mp[t] = ans\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    ans = mp[t] + space + 1\n",
    "                    mp[t] = ans\n",
    "                    ans += 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        last = {}\n",
    "        ans = 0\n",
    "        for t in tasks:\n",
    "            if t in last:\n",
    "                ans = max(ans, last[t] + space)\n",
    "            ans += 1\n",
    "            last[t] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = dict()    # 储存这一任务上一次完成的时间\n",
    "        time = 0\n",
    "        for t in tasks:\n",
    "            if t in d and time < space + d[t] + 1:\n",
    "                time = space + d[t] + 1\n",
    "            else:\n",
    "                time += 1\n",
    "            d[t] = time\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        n = len(tasks)\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            if tasks[i] in d:\n",
    "                if ans - d[tasks[i]] < space + 1:\n",
    "                    ans = d[tasks[i]] + space + 1\n",
    "            d[tasks[i]] = ans\n",
    "            ans += 1\n",
    "        # print(d)\n",
    "        return ans - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = dict()    # 储存这一任务上一次完成的时间\n",
    "        time = 0\n",
    "        for t in tasks:\n",
    "            if t in d and time < space + d[t] + 1:\n",
    "                time = space + d[t] + 1\n",
    "                d[t] = time\n",
    "            else:\n",
    "                time += 1\n",
    "                d[t] = time\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans = 0\n",
    "        last = {}\n",
    "        for i in tasks:\n",
    "            ans += 1\n",
    "            if i in last:\n",
    "                ans = max(ans, last[i] + space + 1)\n",
    "            last[i] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        dict_task=defaultdict(int)\n",
    "\n",
    "        days=0\n",
    "\n",
    "        for i in range(len(tasks)):\n",
    "            days+=1\n",
    "            \n",
    "            task_id=tasks[i]\n",
    "\n",
    "            #while(dict_task[task_id]!=0 and dict_task[task_id]+1+space>days):\n",
    "            #    days+=1\n",
    "            if(dict_task[task_id]!=0 and dict_task[task_id]+1+space>days):\n",
    "                days=dict_task[task_id]+1+space\n",
    "                \n",
    "            dict_task[task_id]=days\n",
    "\n",
    "        return days\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        _next = defaultdict(int)\n",
    "        curr = 0\n",
    "        for days, task in enumerate(tasks):\n",
    "            if curr < _next[task]:\n",
    "                curr = _next[task]\n",
    "            _next[task] = curr + space + 1\n",
    "            curr += 1\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        m = defaultdict()\n",
    "        cur = 1\n",
    "        for task in tasks:\n",
    "            if task in m:\n",
    "                if cur - m[task] -1 < space:\n",
    "                    cur = cur + space - cur+ m[task]+1\n",
    "                m[task] = cur\n",
    "            else:\n",
    "                m[task] = cur\n",
    "            cur += 1\n",
    "        return cur-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        days = 0\n",
    "        cd = {}\n",
    "\n",
    "        for task in tasks:\n",
    "            days += 1\n",
    "            if task in cd and days - cd[task] <= space:\n",
    "                days += space - (days - cd[task]) + 1\n",
    "            cd[task] = days\n",
    "            \n",
    "        return days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = {}\n",
    "        for t in tasks:\n",
    "            ans += 1\n",
    "            if t in cnt.keys():\n",
    "                ans = max(ans, cnt[t] + space + 1)\n",
    "            # 上一次开始的位置\n",
    "            cnt[t] = ans\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        res = 0\n",
    "        # i代表哪一天，j代表任务类型\n",
    "        for i, j in enumerate(tasks):\n",
    "            # 如果已经完成的任务中没有当前的任务类型\n",
    "            if j not in d:\n",
    "                res += 1\n",
    "            else:\n",
    "                # 如果有，并且满足间隔要求，则不需要休息\n",
    "                if i - d[j] > space:\n",
    "                    res += 1\n",
    "                # 不满足，则需要休息\n",
    "                else:\n",
    "                    # 休息的天数\n",
    "                    day = space - (i - d[j]) + 1\n",
    "                    res += day + 1\n",
    "                    # 既然休息了day天，则之前所有的任务的下标减少day天\n",
    "                    for key in d.keys():\n",
    "                        d[key] = d[key] - day\n",
    "            # 每次存储该任务类型是哪一天\n",
    "            d[j]=i\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        result = 0\n",
    "        mapping = {}\n",
    "        for t in tasks:\n",
    "            if(t not in mapping):\n",
    "                mapping[t] = result\n",
    "            else:\n",
    "                if(result - mapping[t] > space):\n",
    "                    mapping[t] = result\n",
    "                else:\n",
    "                    result = mapping[t] + space + 1\n",
    "                    mapping[t] += space + 1\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans, last = 0, {}\n",
    "        for t in tasks:\n",
    "            ans += 1  # 完成该任务，天数+1\n",
    "            if t in last:\n",
    "                ans = max(ans, last[t] + space + 1)  # 看看是否要间隔 space 天\n",
    "            last[t] = ans  # 记录上一次完成时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        \n",
    "        n = len(tasks)\n",
    "        f = defaultdict(lambda:float('-inf'))\n",
    "        i = 0\n",
    "        t = 0\n",
    "        while i < n:\n",
    "            t += 1\n",
    "            if f[tasks[i]] + space + 1 <= t:\n",
    "                f[tasks[i]] = t \n",
    "                i+=1\n",
    "            else:\n",
    "                t = f[tasks[i]] + space\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        res, last = 0, {}\n",
    "        \n",
    "        for task in tasks:\n",
    "            res += 1\n",
    "            if task in last:\n",
    "                res = max(res, last[task] + space + 1)\n",
    "            \n",
    "            last[task] = res\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        Days = {}\n",
    "        res = 0\n",
    "        for i in tasks:\n",
    "            res += 1\n",
    "            if i in Days:\n",
    "                if(res - Days[i] <= space):\n",
    "                    res = Days[i] + space + 1\n",
    "            Days[i] = res\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        \"\"\"\n",
    "            tasks   \n",
    "        \"\"\"\n",
    "        cnt ={}\n",
    "        tot = 0\n",
    "        for t in tasks:\n",
    "            tot+=1\n",
    "            if t in cnt:\n",
    "                tot= max(tot,cnt[t]+space+1)\n",
    "            cnt[t]=tot \n",
    "        return tot\n",
    "                  \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        n = len (set(tasks))\n",
    "        dic = {}\n",
    "        cur = 1\n",
    "        for i in range(len(tasks)):\n",
    "            if tasks[i] in dic and dic[tasks[i]]>=cur:\n",
    "                cur=dic[tasks[i]]+1\n",
    "            dic[tasks[i]] = cur+space\n",
    "            cur+=1\n",
    "        return cur-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        t, d = 0, {}\n",
    "        for x in tasks:\n",
    "            if x in d:\n",
    "                t = max(d[x], t)\n",
    "            t += 1\n",
    "            d[x] = t + space\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans, last = 0, {}\n",
    "        for t in tasks:\n",
    "            ans += 1  # 完成该任务，天数+1\n",
    "            if t in last:\n",
    "                ans = max(ans, last[t] + space + 1)  # 看看是否要间隔 space 天\n",
    "            last[t] = ans  # 记录上一次完成时间\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        ans = 0\n",
    "        pre = defaultdict(lambda: -inf)\n",
    "        for t in tasks:\n",
    "            if ans+1 - pre[t] - 1 >= space:\n",
    "                ans += 1\n",
    "                pre[t] = ans\n",
    "            else:\n",
    "                ans = pre[t] + space + 1\n",
    "                pre[t] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        res = 0\n",
    "        last = {}\n",
    "        for t in tasks:\n",
    "            res += 1\n",
    "            if t in last:\n",
    "                res = max(res, last[t]+space+1)\n",
    "            last[t] = res  #记录上一次完成的时间\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        q = deque([0] * space)\n",
    "        ret = i = 0\n",
    "        while i < len(tasks):\n",
    "            ret += 1\n",
    "            if tasks[i] not in q:\n",
    "                q.append(tasks[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                q.append(0)\n",
    "            q.popleft()  \n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = defaultdict(list)\n",
    "        ret = 0\n",
    "        for i, t in enumerate(tasks):\n",
    "            if d[t] and ret - d[t][-1] <= space:\n",
    "                ret += space - ret + d[t][-1] + 1\n",
    "            d[t].append(ret)\n",
    "            ret += 1\n",
    "        return ret\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d, ret = {}, 0\n",
    "        for t in tasks:\n",
    "            if t in d and ret - d[t] <= space:\n",
    "                ret = d[t] + space\n",
    "            d[t] = ret = ret + 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        day = 0\n",
    "        last = {}\n",
    "        for t in tasks:\n",
    "            day += 1\n",
    "            if t in last:\n",
    "                day = max(day,last[t]+space+1)\n",
    "            last[t] = day\n",
    "        return day\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        result = 0\n",
    "        mapping = {}\n",
    "        for t in tasks:\n",
    "            if(t not in mapping):\n",
    "                mapping[t] = result\n",
    "            else:\n",
    "                if(result - mapping[t] > space):\n",
    "                    mapping[t] = result\n",
    "                else:\n",
    "                    result = mapping[t] + space + 1\n",
    "                    mapping[t] += space + 1\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        result ,last = 0,{}\n",
    "        for t in tasks:\n",
    "            result += 1\n",
    "            if t in last:\n",
    "                result = max(result,last[t] + space + 1)\n",
    "            last[t] = result\n",
    "        \n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        res = 0\n",
    "        last = {}\n",
    "        for t in tasks:\n",
    "            res += 1\n",
    "            if t in last:\n",
    "                res = max(res,last[t] + space+1)\n",
    "            last[t] = res \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        cnt=collections.Counter()\n",
    "        d=1\n",
    "        for x in tasks:\n",
    "            if x not in cnt:\n",
    "                cnt[x]=d\n",
    "                d=d+1\n",
    "            else:\n",
    "                if d-cnt[x]<space+1:\n",
    "                    d=cnt[x]+space+1\n",
    "                    cnt[x]=d\n",
    "                    d=d+1\n",
    "                else:\n",
    "                    cnt[x]=d\n",
    "                    d=d+1\n",
    "           # print(cnt,d)\n",
    "        return d-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        d = dict()\n",
    "        day = 0 \n",
    "        for i in range(len(tasks)):\n",
    "            if tasks[i] not in d.keys():\n",
    "                day += 1\n",
    "                d[tasks[i]] = day\n",
    "            elif day - d[tasks[i]] >= space:\n",
    "                day += 1\n",
    "                d[tasks[i]] = day\n",
    "            else:\n",
    "                day += space - day + d[tasks[i]] + 1\n",
    "                d[tasks[i]] = day\n",
    "\n",
    "        return day"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def taskSchedulerII(self, tasks: List[int], space: int) -> int:\n",
    "        n = len(tasks)\n",
    "        days = defaultdict(int)\n",
    "        cur = 0\n",
    "        for task in tasks:\n",
    "            if task not in days:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = max(days[task], cur) + 1\n",
    "            \n",
    "            days[task] = cur + space\n",
    "            \n",
    "        return cur"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
